package com.zdp.leetcodeMiddle;

import com.zdp.剑指offer.ListUtil;
import com.zdp.util.ListNode;

import java.util.ArrayList;
import java.util.List;

public class 重排链表 {
    /*
    * 题目描述：（单链表重排）
    * 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
    将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
    你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
    示例 1:
    给定链表 1->2->3->4, 重新排列为 1->4->2->3.
    示例 2:
    给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/reorder-list
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    * */
    public static void main(String[] args) {
        ListNode list = ListUtil.createList(new int[]{1, 2, 3, 4});
        ListUtil.outList(list);
        重排链表 demo = new 重排链表();
        demo.reorderList(list);
        ListUtil.outList(list);
    }
    public void reorderList(ListNode head) {
        //由于是单链表，所以不能简单的一头一尾指针，没有前置指针，不能指到前一个元素
        //可以使用快慢指针，将链表分段，后半段反转链表，然后将反转后的链表插入到前半段链表中
        if(head==null)
            return ;
        ListNode quick = head;
        ListNode slow = head;
        //获得中间的指针，快慢指针
        while(quick!=null&&quick.next!=null){
            quick = quick.next.next;
            slow = slow.next;
        }
        //获得需要反转的链表的头节点
        ListNode reverHead = slow.next;
        slow.next = null; // 切断前半部分和后半部分的连接
        //反转链表 ---> 使用哨兵，然后利用头插法
        ListNode pp = new ListNode();
        pp.next = null;
        while(reverHead!=null){ //利用头插法反转链表
            ListNode temp = reverHead;
            reverHead = reverHead.next;
            temp.next = pp.next;
            pp.next = temp;
        }
        //反转链表后，开始依次插入前半段的，遍历后半段的即可,画图模拟一下
        reverHead = pp.next;
        ListUtil.outList(reverHead);
        ListNode p = head;
        while(reverHead!=null){
            ListNode temp = reverHead;
            reverHead = reverHead.next;
            temp.next = p.next;
            p.next = temp;
            p = temp.next;
        }

    }
    /*
    * 解法二：好像使用一个ArrayList 数组来存放各个结点。利用数组可以用下标快速索引的特点
    * 来快速得到要使用的 链表结点  但这个办法要占用的空间较多
    * */
    public void reorderList1(ListNode head) {
        List<ListNode> array = new ArrayList<>();
        ListNode p = head;
        while(p!=null){
            array.add(p);
            p = p.next;
        }
        //然后就可以利用下标来进行插入操作了
        int i=0,j=array.size()-1;
        while(i!=j&&i+1!=j){
            ListNode a = array.get(i);
            ListNode b = array.get(j);
            //b插入到a
            b.next = a.next;
            a.next = b;
            i++;
            j--;
        }
        array.get(j).next = null;
    }
}
